package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Stack;

/**
 *    基于深度优先的路径查找
 */
public class DepthFirstPaths {
    private boolean[] marked;           //索引代表顶点，值表示当前顶点是否已经被搜索
    private int s;                      //起点
    private int[] edgeTo;               //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点

    public DepthFirstPaths(Graph g,int s){
        marked = new boolean[g.V()];
        edgeTo = new int[g.V()];
        this.s=s;
        dfs(g,s);
    }
    /**
     * 使用深度优先搜索找出G图中v顶点的所有相邻顶点
     * @param G
     * @param v
     */
    private void dfs(Graph G, int v) {
        marked[v]=true;
        for (Integer integer : G.adj(v)) {
            if (!marked[integer]){
                edgeTo[integer]=v;
                dfs(G,integer);
            }
        }
    }

    /**
     * 判断v顶点与s顶点是否存在路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return marked[v];
    }

    /**
     * 找出从起点s到顶点v的路径(就是该路径经过的顶点)
     * @param v
     * @return
     */
    public Stack<Integer> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Stack<Integer> path = new Stack<>();
        for (int x=v;x!=s;x=edgeTo[x]){
            path.push(x);
        }
        path.push(s);
        return path;
    }

}
